Hebuter Daily Training 201810

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

emmm.daily trainning第一天. 题目原题是cf上的
Codeforces Beta Round #9 (Div. 2 Only)

A Die Roll

题目大意:

有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个
地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去
他想去的地方.Y,W已经投掷了.求D获胜的概率.输出.0/1表示不可能获胜
1/1表示一定获胜.

题解:

根据题意的Note可知.假设$a = \max(Y, W);如果D >= a$.是$D$获胜.所以只要求
$(6-(a-1))/6$.分子分母约分.假设$x = 6 - a + 1. y = 6. z = gcd(x, y);
ans = (x/z)/(y/z). $可以知道不可能有$0/1$的情况

`

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int Y,W;
    cin >> Y >> W;
    int a = max(Y, W);
    int x = 6 - a + 1, y = 6, z = __gcd(x, y);
    cout << x/z << "/" << y/z << endl;
    return 0;
}

B Interestring graph and Apples.

题目大意:

一个无向图被称作interesting.当且仅当它的顶点只属于一个
funny ring.funny ring的定义就是一个环可以遍历所有顶点
只有一次.一个圈也是一个funny ring.最少添加多少条边使得
当前图成为interesting.输出字典序最小的添加顺序.

题解:

可以肯定的是interesting graph就是一个funny ring.它有n个顶点
n条边.因为n个顶点n-1条边是树.多一条边就有一个环.如果再多一条边
就是多余两个环了.不满足定义.

一个图是一个funny ring当且仅当满足下面两个条件
A1. 每个点的度数是2.
A2. 图是连通的

现在我们找到当一个图不是funny ring.但是通过添加边.可以转换成funny ring
B1. m < n. 边的数量少于点的数量.
B2. 没有环
B3. 每个点的度数都不超过2

我们需要添加一些边使得这些条件都满足.并且这个添加序列是字典序最小的.
所以我们按照如下规则添加边(i,j).

  1. i,j两个点的度数都小于2.(打破条件B3)
  2. i,j属于两个不同的连通分量(打破条件B2)
  3. (i,j)字典序最小

我们什么时候不能再添加边.当没有环的时候.每个连通分量是一颗树.因此至少
有一个点的度数小于2(根).如果有两个连通分量.连接的话就可以打破条件B1-B3
所以图连通,没有环,每个点的度数不超过2.意味着获得的图知识一条链.我们可以
连接它的结束的点获得一个funny ring.

通过上面的描述.算法:

  1. 检查是否满足条件A1,A2.如果满足.输出”YES” 和 0
  2. 检查是否满足B1.B2.不满足.输出”NO”
  3. 输出”YES” 和 n-m.(加入n-m条边)
  4. 按照描述添加边i,j.当(i,j)添加成功.输出”i j”
  5. 找到点i,j度数不超过2(i和j可以相等.如果n = 1). 输出 “i j”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;


#define MAX_N 55
int n,m;
int fa[MAX_N];
int in[MAX_N];
vector<int> G[MAX_N];
bool has[MAX_N];

struct P{
    int u,v;
};

void init(){for(int i = 0; i < n; ++i) fa[i] = i;}
int findd(int x) {return x == fa[x] ? x : fa[x] = findd(fa[x]);}
void unite(int x, int y) {x = findd(x); y = findd(y); fa[x] = y;}
bool same(int x, int y) {return findd(x) == findd(y);}


bool dfs(int u, int fa){
    int sz = G[u].size();
    has[u] = true;
    for(int i = 0; i < sz; ++i){
        int v = G[u][i];
        if(v == fa) continue;
        if(has[v] || dfs(v, u)) return true;
    }
    return false;
}

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int u,v;
    while(cin >> n >> m){
        init();
        memset(has, false, sizeof(has));
        memset(in, 0, sizeof(in));
        for(int i = 0; i < n; ++i) G[i].clear();
        for(int i = 0; i < m; ++i){
            cin >> u >> v;
            ++in[--u]; ++in[--v];
            unite(u, v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        bool flag = false;
        bool two = true; // 是不是都是2
        int i;
        for(i = 0; i < n; ++i) {
            two &= (in[i] == 2 && same(0, i));
            if(in[i] > 2) {flag = true; break;}
        }
        if(two){ // 满足所有点在一个联通快并且是一个环
            puts("YES\n0"); continue;
        }
        if(flag || m >= n) {puts("NO"); continue;}
        // 判断是不是有环
        for(int i = 0; i < n; ++i){
            if(!has[i]) {
                if(dfs(i, -1)) {flag = true; break;}
            }
        }
        if(flag) {puts("NO"); continue;}
        puts("YES");
        printf("%d\n", n - m);
        vector<P> vp;
        for(int i = 0; i < n; ++i){
            if(in[i] >= 2) continue;
            for(int j = 0; j < i; ++j){
                if(in[j] < 2 && !same(i, j)) {
                    unite(i, j); // 连接i,j
                    ++in[i]; ++in[j];
                    vp.push_back((P){i, j});
                }
            }
        }
        // 最后都在一个联通块.只剩下两个或者一个度数<2的
        u = v = -1;
        for(int i = 0; i < n; ++i){
            if(in[i] < 2) {
                if(u == -1) u = i;
                else {v = i; break;}
            }
        }
        // 只有一个结点的时候
        if(v == -1) v = u;
        vp.push_back((P){u, v});
        for(int i = 0; i < n-m; ++i){
            if(vp[i].u > vp[i].v) swap(vp[i].u, vp[i].v);
            printf("%d %d\n", vp[i].u+1, vp[i].v+1);
        }
    }
    return 0;
}

emmm.第二天.

C.三角形

题目大意:

在$n*m$边长的网格中选择三个点可以组成的三角形个数。

题解

$n*m$边长的网格有

$(n+1)(m+1)$ 个点

我们要选择三个来组成三角形.

方案数就是$total=C_{(n+1)(m+1)}^3$.

但是这是所有情况.有些三个点是共线的.所以我们只要找出三个点共线的方案数$other$.

答案$ans=total-other$

在属于$other$的有下面三种情况:

  1. 横着的线有$m+1$条(横轴是$n$.纵轴是$m$).$other_1=(m+1)C_{n+1}^3$
  2. 竖着的先有$n+1$条.$other_2=(n+1)C_{m+1}^3$
  3. 斜着的.有斜率是正的斜着的.也有斜率是负的.但是我们只要算出斜率是正的.乘$2$即可.

解释一下第三种情况的计算：

斜线可以画一画图.

我们以$(0,0)$ 到 $(x,y)$ 的线$l_1$作为标准.$l_1$这样的线有$(n+1-x)(m+1-y)$条.

(emmm.这里也可以画一画).

这条线上的点是格点的有$x=gcd(x,y)-1$个

(emmm.这个结论详见《挑战程序设计竞赛》2.6章:数学问题的解题窍门).

所以只要$x>=1$.那么两端的点就可以和这$x$个点中任意一个组成一种方案.

$l1$这种线的方案数就是$2x(n+1-x)(m+1-y)$

所有$1<=x<=n.1<=y<=m$计算出来$other_3$.

最后$ans=total-(other_1+other_2+other_3)$.

时间复杂度$O(n*m)$

emm.顺便提一下.注意结果溢出.orz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL n, m;
LL C3(LL n) {
    return n*(n-1)*(n-2)*1LL/6LL;
}

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    ++n; ++m;
    LL ans = C3(n*m) - m*C3(n) - n*C3(m);
    for(int i = 1; i < n; ++i){
        for(int j = 1; j < m; ++j){
            int x = __gcd(i, j) - 1; // (0, 0) 到 (i, j)中格子数目.不包含两端
            if(x >= 1) { // 多于一个
                ans -= (n - i) * (m - j) * x * 2LL;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
emm.坚持原创技术分享，您的支持将鼓励我这个小菜鸡的创作！